struct Node {
	int val;
	struct Node* left;
	struct Node* right;
	struct Node* next;
};

struct Node* connect(struct Node* root)
{
	if (root == NULL)
		return root;

	struct Node* leftMost = root;
	while (leftMost->left != NULL) {
		struct Node* head = leftMost;

		while (head != NULL) {
			head->left->next = head->right;
			if (head->next != NULL)
				head->right->next = head->next->left;
			head = head->next;
		}

		leftMost = leftMost->left;
	}

	return root;
}
